package 数据结构专栏.A_二叉树专栏.E_前缀树;

/**
 * 实现一个前缀树：
 * https://leetcode.cn/problems/implement-trie-prefix-tree/solution/by-lfool-k6hb/
 */
class Trie {
    class TrieNode {
        boolean val;
        TrieNode[] children = new TrieNode[26]; //26个英文字母
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (p.children[i] == null){
                p.children[i] = new TrieNode();
            }
            p = p.children[i];
        }
        p.val = true;
    }

    public boolean search(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (p.children[i] == null) return false;
            p = p.children[i];
        }
        return p.val;
    }

    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for (char c : prefix.toCharArray()) {
            int i = c - 'a';
            if (p.children[i] == null) return false;
            p = p.children[i];
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        trie.search("apple");   // 返回 True
        trie.search("app");     // 返回 False
        trie.startsWith("app"); // 返回 True
        trie.insert("app");
        trie.search("app");     // 返回 True

    }
}

